perm filename GEM[0,BGB]17 blob
sn#206964 filedate 1974-08-27 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00012 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {⊂CFJ≤G<NαGEOMETRIC MODELING THEORY.λ30I425,0P6JCFA} SECTION 1.
C00006 00003 {I110,0}⊂1.1 Kinds of Geometric Models.⊃
C00012 00004
C00018 00005 In passing from space oriented models to object oriented
C00022 00006
C00027 00007 Beyond the particular kinds of geometric models, four general
C00030 00008 {|λ10JA}
C00032 00009 {I110,0}⊂1.2 Polyhedron Definitions and Properties.⊃
C00036 00010
C00039 00011 ⊂1.3 Camera, Light and Image Modeling.⊃
C00042 00012 ⊂1.4 Related Modeling Work.⊃
C00046 ENDMK
C⊗;
{⊂C;FJ;≤G;<N;αGEOMETRIC MODELING THEORY.;λ30;I425,0;P6;JC;FA} SECTION 1.
{JC;FD} GEOMETRIC MODELING THEORY.
{λ10;W250;JAFA}
1.0 Introduction to Geometric Modeling.
1.1 Kinds of Geometric Models.
1.2 Polyhedron Definitions and Properties.
1.3 Camera, Light and Image Modeling.
1.4 Related Modeling Work.
{λ30;W0;I950,0;JUFA}
⊂1.0 Introduction to Geometric Modeling.⊃
In the specific context of computer vision and graphics,
<geometric modeling> refers to the construction of computer representations
of physical objects, cameras, images and light for the sake of
simulating their behavior. In Artificial Intelligence, a geometric
model is a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that it is quantitative and numerical rather than qualitative and
symbolic. The notion of a world model requires an external world
environment to be modeled, an internal computer environment to hold
the model, and a task-performing entity to use the model. In
Geometry, modeling is a synthetic problem, like a construction with
ruler and straight edge; modeling problems require an algorithmic
solution rather than a proof. The word <geometric> is an appropriate
adjective to this kind of modeling in that it is a combination of the
Greek words ≤gho≥ (world) and ≤metria≥ (measuring) which is exactly
the activity to be automated. {Q}
{I110,0;}⊂1.1 Kinds of Geometric Models.⊃
The main problem of geometric modeling is to invent methods
for representing arbitrary physical objects in a computer. For the
present discussion, the class of physical objects is restricted to
objects that are solid, rigid, opaque, and macroscopic with a
mathematically well behaved surface. Such objects include: the earth,
chairs, roads, and plastic toy horses; other objects, for which
models will not be attempted, include glass, fog, hair, Jello,
liquids and cloth. Physical objects can move about in space with the
restriction that two objects can not occupy the same space at the
same time. The scope of the modeling problem can be appreciated by
examining the models listed in Box 1.1.
{|;λ10;JA}
BOX 1.1{JC} TEN KINDS OF GEOMETRIC MODELS.
{↓}
Space Oriented:
1. 3-D Space Array.
2. Recursive Cells.
3. 3-D Density Function.
4. 2-D Surface Functions.
5. Parametric Surface Functions.
{↑;W640;}
Object Oriented:
6. Manifolds.
7. Polyhedra.
8. Volume Elements.
9. Cross Sections.
10. Skeletons.
{|;λ30;JU;W0,1260,0,1900;}
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirable properties
of <spatial addressing> and <spatial uniqueness> in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to the property that physical solids can not occupy
the same space simultaneously. A first drawback of the space array
idea is illustrated by the apparently legal FORTRAN statement:
{≤J;JC} DIMENSION SPACE(100000,100000,100000)
\The problem with such a dimension statement is that no present
day computer memory is large enough to contain a 10≤15≥ element
array. Smaller space arrays can be useful but necessarily can not
model large volumes with high resolution. A further drawback of space
arrays is that objects and surfaces are not readily accessible as
entities; that is a space array lacks the property of
<object coherence>. In computer graphics, the term <coherent>
denotes both the quality of holding together as parts of the same
mass and the quality of not changing too drastically from one point
to the next. The meaning of <coherent> approachs the mathematical
notion of topologically connected and locally continuous. The word is
used to refer to the frame coherence of a film as well as to
the object coherence of a model.{≤G;W0,1260,150,1800;}
The space array idea can be salvaged by grouping blocks of
elements with the same value together; the addressing process
becomes more complicated but the overall memory required is reduced
and the two desired properties can be maintained. One way of doing
this (which has been discovered in several applications) is
<recursive cells>; the whole space is considered to be a cell; if the
space is not homogeneous then the first cell is divided into two (or
four or eight) sub cells and the criterion is applied again. This
technique allows the spatial sorting of objects when the object
models can be subdivided at each recursion without losing their
properties as objects.
Another salvageable naive modeling idea is that arbitrary
objects can be expressed as algebraic functions. In physics,
physical objects are frequently referred to as three dimensional
density functions W=≤r≥(X,Y,Z). Unfortunately such density functions
can not be written out for objects such as a typing chair or a
plastic horse without resorting to a programming language or an
extensive table (which is equivalent to the space array model).
Objects that are essentially 2-D can be approximated by a surface
function Z = F(X,Y). For example landscape may be represented by
geodetic maps in such a 2-D fashion.
By definition, a function is single valued; consequently the
description of even modestly complicated objects cannot be expressed
by giving one coordinate, e.g. Z, as a function of the other two,
e.g. X and Y. It is necessary either to adopt parametric functions or
to subdivide the object into portions that can be described by simple
functions of Cartesian variables. The former course involves
establishing a system of surface coordinates (U,V), latitudes and
longitudes, on the object in which functions for the X,Y,Z locus of
the object's surface are expressed. The advantage of parametric
functions is that extended arbitrary curve surfaces can be expressed;
some of the disadvantages are that parametric curves may be self
intersecting, they are not easy to modified locally, and the
functions become impractical before the shapes of mundane artifacts
can be achieved. Consequently parametric representations are combined
with object subdivision, which is
called <segmentation>. The process of usefully segmenting an object
without destroying its coherence is a major problem requiring the
combination of spatial, functional and objective representations.{Q;I100,0;}
In passing from space oriented models to object oriented
models, I wish to note that sophisticated representation of time is
beyond the scope of this work. Although an advanced problem solving
robot will need to run world simulations along multiple time paths,
the discussion will concentrate on representing the geometry of the
world at a single moment in time.
After existence in space and time, another general property
of physical objects is that they can be enclosed by an unbroken two
dimensional surface with an unambiguous inside and outside; which
touchs upon the mathematical topic (celebrated in song by Tom Lehrer)
of the algebraic topology of locally Euclidean transitions of
infinitely differentiable oriented Riemann manifolds. A <manifold>
is the mathematical abstraction of a surface; a <Riemann> manifold
has a metric function; an <oriented> manifold has a unambiguous
inside and an outside; the phrase <infinitely differentiable> can be
taken to mean that the surface is smooth; and the phrase <locally
Euclidean transitions> refers to the process of segmenting the object
into portions that can be approximated by relatively simple
functions. In particular, the 2-D Riemann submanifold embedded in
3-D Euclidean space is the mathematical object that comes closest to
representing the shape and extent of the surface of a physical
object; such manifolds are conveniently approached through the
topology of surfaces which in turn is computationally approached by
means of polyhedra.
One way to describe the topology of a 2-D Riemann submanifold
embedded in a 3-D Euclidean space is in terms of three kinds of
simplex: the 0-Simplex (or vertex), the 1-Simplex (or edge), and the
2-Simplex (or triangle). In topological analysis 2-D Riemann
submanifolds may be divided into faces, edges and vertices such that
Euler's equation F-E+V=2-2*H is satisfied (where F is the number of
faces, E is the number of edges, V is the number of vertices and H
is the genus or number of handles of the manifold); and such that the
surface of the manifold can be approximated by local functions over
each face which are Euclidean and which fit together smoothly at all
the edges. By introducing a sufficient (but finite) number of
triangles the manifold can be approximated to within any epsilon by
constant functions, yielding the geometric object called the
<polyhedron>.
One advantage of a polyhedral model is its
connected surface topology of faces, edges and vertices. Such a
surface can be subdivided without losing its coherence or the
coherence of the object. The disadvantages of polyhedra include the
lack of spatial uniqueness and spatial addressing which necessitates
computation to be done to detect and prevent spatial conflict and to
find the portions of an entity occupying a given volume. Another
feature of polyhedra (which can be an advantage or disadvantage) is
that all the (<Gaussian>) curvature happens suddenly at the vertices;
however by associating higher order approximation functions with
each face the model of a continuous 2-D manifold can be made which is
a more conventional curved object representation. Nevertheless,
polyhedra are intrinsically a general curved object representation.
Returning to the survey, arbitrary objects can also be
described by listing a set of cross sections taken at a sufficient
number of cutting planes; this is how the shape of a ship's hull or
an airplane's wing is specified. Cross sections have the interesting
feature of good space modeling on one axis. Forsaking arbitrary
shaped objects, large classes of things can be described in terms of
a small set of basic volume elements. For example, Roberts (63)* and
others have built models of familiar objects using only rectangular
and triangular right prisms. Arbitrary solid polyhedra can be
constructed out of tetrahedra (the 3-simplex); however no significant
general modeling system exists using this potentially interesting
approach.
Skeletal models are based on abstracting an object into a
stick figure and by associating a diameter or set of cross sections
with the sticks. In particular, spine cross section models have been
pursued at Stanford by Agin (72) and Nevatia (74). Spine cross
section models have the advantage of being able to express many
objects in a concise form suitable for recognition, but they cannot
be used directly for arbip ↓∪πKeπ≠#πC/→84(hP&≠'v 33eb↓β'QεKMβ?7#↔9β/≠↔≠WbβS=β⊗+CK↔≡+;QβεCgO'≡ 1β?⊗S↔∂S~β d4W;↔π-ε;↔?7/#K'
εk?∪↔g→↓βO.≠!βπ~↓β eπ≠↔SMαβ?→β∨β#↔K/→β?Iαβ eβ≡+SM↓ε{_4+.s∂?;v+∂S↔"↓βOW⊗3π∂∃αβC?'w#M9αO!↓β'~↓β';&+K↔O&K;≥↓π#=β;␈#∃↓β&CπQ↓π##∀4ScK↔πfKSeyαβS#π"βS#∃αβK? ␈!β'9αα←';};Kπ⊃?→βS#/≠'M↓E;';??∪π⊃↓β9E%β≡{W3⊂hSSπ3Zβπ ?/!1β←∂→β¬β⊗c?∂/~β←?Kf!β π≡+⊃β?rβ¬↓β>+?7↔'∪'
βn{∪↔1ε≠?;OO≠S';8h+?;gIβ?→πβ?';'→1↓β≡Kk∃β}1β 3}≠-1↓ε ;⊃β
βS←=πβπ∨∃∧b&NAπ≠W K␈+S';*β;π7. 4*~Lr∩NB ~∃84WZ!QnHyA1A]0=A1 ⊃YAnHyMA1βX4+yRαCπK.sS#↔≡Kk↔⊃εsπ7↔~βπ;⊃εsW7↔⊗ 3Mβ∂∪∃βK.3↔K↔v≠↔MβfKOS↔"β'9α≡+∂S'}q↓EEsλ4(4P0& /K?;⊃π##∃βε KS'∨+3πIε[';∪~β?→β>+?7↔'∪'
βn{∪↔3~aβ≠?/⊃β∨↔v+Kπ0hSCWKε{O∃↓εk?∪↔fK;≥β&+∂#;O W↔Mαβ∪↔O/∪[∃β∨β↔∂'∞aβ7↔w#'?9αβπ;⊃εKO?3∂#'?9Ph+CK␈#?Sgε)β';∨#π;∂*↓βOS↔+∂SW⊗)1↓↓πβπKS~↓βSK.)βOS↔+∂SW⊗)1↓↓αβK↔O}cWS'}p4+3Nk'S↔"βOSK.≠SWK*a↓βπv!βCK}≠↔∪W⊗)β∨↔v+KπS.!βOS↔+∂SW⊗)9αO/β↔K≠N≠'π3gI04+&C∃↓βπ∪?S?'KC∃βNsOSπv≠∃↓β∨#KW∂'+K∃βO→↓β¬εk↔7?↔I↓β↔63'∂'.s∂eβ&+∂#;O W∀4V∪πO↔"β?9β∨#?K'v9β∨↔v+Kπ3OSπS'}sM↓↓GβK?S␈#gC↔~Iβ←#N≠!β∂∞qβ ∃αβ ?Wv!βS<hSOC↔≡K≠'
αβ∂πO/→↓#'w≠Sπ;≡+M%↓ε M↓β&C∃β?≡≠πO'}q↓β∪.kπ;∪~q↓↓αε KSMαβSK↔(h+OS↔+∂SW⊗)β'Mε ↓β7.k?Keεkπ;π>+7↔;"βS↔∂Fs'GW*↓β?→ε{K∨πvKk';:βS#∃αβ←#?f(4+WvK[↔K≡)β?→αβ∪'O≡{WKO*βπMβ
↓βSK.)β∪π& ↓βO'∪W∂S/∪∃1β>C↔K∃ε{ +↔∨#M↓β∂∪∀4+≡{7C?≡+⊃↓β}1βOW⊗{ +↔∨#M9↓ααK↔O}cWS'}qβ3'nKS↔⊃π≠SKW∨#WK∃αβ'Mβ
β7↔7␈∪d4+∞≠∂↔O≡K;≥β&+∂#;O W∃1π;#↔K*β∪↔C.s∪';:β?9β
βOC↔≡K≠'↔"βO∂πf)β?→εK;S↔⊗+OP4V#'≠≠/∪↔;Qεk?∪↔g→βπK*βK↔S⊗K↔[↔"↓β?Iε+[↔9ε;↔;↔⊗ S↔⊃rα≠';∞c3e1πβK?∂.#WK∀hS∨↔;/∪πS↔"↓βOS↔+∂SW⊗)↓β∂}s∂↔Kw→↓βSF)↓βS⊗ ∪∃7}3→↓β⊗+S←↔.q↓βO&{K';:↓βπ; h+K↔≡{7CW&K;≥β
↓β7?&+1mβv 7↔3JβK↔∂}kCWSNs≥↓β&C∃β∪/#π'3~↓β?→ε β7?&+1↓β∂_4+SF+eβπ⊗)β;↔.#↔⊃βO→β¬β>{?⊃βN#↔¬β6{Iβ↔G#↔;∪Ns≥β∂}kCWS∂#'?;∞aβK↔≡{WK∂/→84(hP&S#*β∪π;>+I↓β&yβ ∃ε [?'&+⊃β'~βS=↓εk'OS∞[∃βSF)β∨↔v+Kπ1εk?∪↔fK;≤4W#↔∂#vKGW↔~β≠?Iπ##∃β>+?7↔'∪'
βn{∪↔1αβ'SO.c→9↓∧;'[↔rβ¬β7}#↔3'v9↓βK.;'7∀hS'Q↓α↓β∂πr↓↓β *↓↓↓βNkCK?6+⊃↓↓αβ e↓αβCK?&{SgCNs≥1↓α↓↓↓↓αβCπK'→7SK.+';≥`h+K↔≡{3WSN{973Nk'S'v9↓βπv!βCK}≠↔∪W⊗ 17∨.s↔Kπ&K;≥mπ;'S#␈+Q↓β
β∨??"β πON_4+∨.{7↔S⊗K
β7}#↔1β&C∃β∨.s↔KπbβS↔∂Fs'GW/→βπ7εc'≠eπ##∃β⊗ ∂/∨⊗{W;⊃εs?'O*p4(3oqXAEAnT x4*∀za↓Es⊂'n*∨qα∩⊗≤JJε
d)αBJ⎇α⊗JRL*Mα~⎇⊃α¬α<*>6⊗%∩&
αlz∩⊗1ph+lπph(%ErαOCπ&Kπ1β∞#∪K↔∨≠';≥ph(%IrαOCπ&Kπ1β.s'GW.s↔OMph(%Mrα? +.≠Qβ∂}C↔K↔v≠∃84PIQ9α∨+K≠π≡)β∂?F+K↔;≡)84(K)9αOF C∃β>+;↔K∞c'Seph+ny←9UAA←p4(%2qα3π⊗;∃β↔G#↔;Qπ;'S!εC'∨!π∪↔O?g+S'?rp4(%:qα↔π∨Iβ7?&K≠'π⊗c'Seph(%arαOW'& '3O#eβ≠␈⊃βC#O≠'∂πbβO'7.cπS'}q84(KI9α↔63'∂'.s∂eβ}1β7↔n{Keβ∞s⊃β∂}kCWS∂#'?9π+O∃0hQ↓↓↓α↓↓↓EαqαOWO#π 'fKSeβ6{Iβπ/#?7π&K
β7}#↔1β∞≠GW'≡KS'?rp4+ocX!MA\RWx4PJS=β&C∃β /≠Qβ?2↓β7eε[;?←f+∪∨∃bβS#'~βOWK6+eβ'~↓β∂?oβ3↔S*qαπMε{_4+&C'MβN+πI1β e]Qb↓βS#/∪∃βπ⊗)β;=ther significantly different kinds of
simple geometric models. The desirable properties that have turned up
in this survey are listed in Box 1.2. The final desirable property is
that there be some hope that the computer can derive the model by
measurements it can make itself, although it is quite likely that one
model will be best for input and another model will be best for
simulation.{Q}
{I110,0;}⊂1.2 Polyhedron Definitions and Properties.⊃
In computational modeling, definitions are not used
formally, but are rather employed piecemeal in terms of individual
properties which may or may not be present as polyhedra are generated
and processed. In particular, the properties listed in Box 1.3 (given
in order of relevance) can be taken as a working definition of a
polyhedron for modeling a physical object.
{|;λ10;JA}
BOX 1.3 {JC} PROPERTIES OF POLYHEDRA.
{JA;T140,597;FA↓}
1. Eulerian∞.
2. Surface Homogeneity∞.
3. Trivalence∞.
4. Face Planarity∞.
5. Solidity∞.
6. Simply Connected Faces∞.
7. Face Convexity∞.
8. Edge Aplanarity∞.
{↑;W600;T-1;}
Satisfies the Euler equation: F-E+V=2-2*H.
The polyhedron does not intersect itself.
All vertices and faces have three or more edges.
All vertices of a face are coplanar.
The volume measure is nonzero, finite and positive.
Face perimeters have one loop of edges.
All the faces are convex.
Faces which share an edge are not coplanar.
{|;λ30;JU}
Topologically, the surface elements of a polyhedron form a
graph that satisfies Euler's F-E+V=2-2*H equation; where as before F,
E and V are the number of faces, edges and vertices of the
polyhedron; and where H is the number of holes in (or genus of) the
polyhedron. However, not all Eulerian graphs of faces, edges and
vertices correspond to the usual notion of a solid polyhedron without
the surface homogeneity and trivalence restrictions. Surface
homogeneity is the property that for any point on the polyhedron a
small enough sphere will cut from the surface a region homeomorphic
to a disk; this restriction implies that the surface cannot
intersect itself and that an edge can belong to only two
different faces. The trivalence restriction insures that there are
no degenerate two edged faces or one edged vertices; although a two
edged vertex has a reasonable interpretation it is excluded by
trivalence for the sake of face-vertex duality and canonical form.
The last property, of aplanarity of faces with a common edge, is also
for the sake of canonical form and is sacrificed to face convexity
when necessary.
Geometrically, the faces of a polyhedron are planar, that is
lie in a plane. It is also frequently relevant to further restrict
the faces of a polyhedron to be convex, that is to require that every
possible line segment between points of a face is contained within
the face. To assure solidity, the volume measure must be restricted
to be finite and positive; this restriction orients the surface to
have an exterior and an interior in the expected fashion. This
restriction excludes non-orientable structures such as Mobius bands
and Klein bottles for which the volume measure is undefined; however
the restriction will be relaxed in Chapter 5 in order to
exploit the concept of negative volumes.
The working definition was derived from more formal
definitions such the following which defines a polyhedron as a
special kind of a two dimensional manifold:
{λ7;W100,1160;}
\"A polyhedron is a connected, unbounded two-dimensional
manifold formed by a finite set of non-re-entrant, simply-connected
plane polygons."
{λ30;JR} - Coxeter, Regular Polytopes (Coxeter 1963).
{W0,1260;I∂20,0;
}\In a <connected> manifold there exists a path between any two
points that does not leave the manifold. An <unbounded> manifold is
one with no cuts or gaps in its surface, that is no boundaries. A
polyhedral manifold is composed of planar, simply-connected,
non-re-entrant polygons; that is flat polygons with a perimeter of
edges that form one loop that doesn't intersect itself. The
polyhedron restrictions and properties are directed towards modeling
physical objects and are maintained by computational mechanisms;
consequently the word <polyhedron> comes to represent an intent,
rather than the fulfillment of any particular set of defining
properties.
⊂1.3 Camera, Light and Image Modeling.⊃
Common to both computer graphics and vision is the necessity
to model cameras, light and images so that pictures may be
synthesized or analyzed. The basic camera model has eight degrees of
freedom, three in location, three in orientation and two in
projection:{λ10;
JA} Location: CX, CY, CZ Vector to camera lens center.
Orientation: WX, WY, WZ Orientation vector.
Projection: AR, FR Aspect Ratio and Focal Ratio.{λ30;JU}
\The orientation vector is explained in Section 3.3, the perspective
projection is defined in Section 3.4, and the derivation of the
camera parameters is the main topic of Chapter 9. In modeling light
and physical objects, the most important and difficult property to
simulate is opacity. Techniques for modeling opaque objects are
presented in Chapter 4.
Finally, an image is a 2-D geometric object representing the
content of a rectangle from the pattern of light of light formed by a
thin lens on a television vidicon. The video image is the interface
to the external reality. Image modeling is analogous to 3-D geometric
modeling, since the same tradeoffs between spatial structure and
object structure arise. A 2-D image may be represented as a video
raster, which is a 2-D space array; or as a set of feature loci,
which is an object oriented description. Image structures and
processors for generating and comparing image representations are
discussed in Chapters 7 and 8. Together camera, light and image
modeling are the essential elements required to apply a geometric
model to computer vision.
⊂1.4 Related Modeling Work.⊃
Although geometric modeling per se has a long history and a
rich literature in mathematics, physics and engineering, very little
such modeling has been done using a computer at the level of detail
required for visual perception. This level falls between the
generality typical in physics and mathematics and the specificity
typical of engineering. Computer science research in geometric
modeling has already been cited in Section 1.2; similar ideas are
available from computer graphics sources (Newman and Sproull 73). In
computer graphics, the typical modeling paper invariably has a long
discussion about the implementation of a node/link modeling language
(CORAL, LEAP, ASP, and others) and very little discussion on how
the actual geometric modeling is to be done in the given language. In
mathematics, I have found the work of the Canadian geometer Coxeter,
(Coxeter 61) and (Coxeter 63) to be my best source of ideas relevant
to modeling; along with the observations from recreational
mathematicians (Gardner 59), (Gardner 61) and (Stewart 70); and
geometry textbook authors (Eves 65), (Snyder 14) and (Graustein 35).
The translation of Hilbert's book (Hilbert 52) presenting Geometry
for the non-mathematician is also a good source of ideas. From
Physics, material on classical mechanics is useful in modeling
rotation and inertia tensors (Goldstein 50), (Feynman et al 63) and
(Symon 53). In engineering, books on geodetic surveying, mechanical
drawing and architectural drawing contain ideas relevant to modeling
particular classes of objects; I have selected (Luzadder 71) and
(Muller 67) almost at random, as introductions to engineering and
architectural drawing, respectively.